/*
 * topological-hex, a program to compute combinatorial hexahedral meshes.
 *
 * Copyright (C) <2018> <Université catholique de Louvain (UCL), Belgique>
 *
 * List of the contributors to the development, description and complete
 * License: see LICENSE file.
 *
 * This program (topological-hex) is free software:
 * you can redistribute it and/or modify it under the terms
 * of the GNU General Public License as published by the Free
 * Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program (see COPYING file).  If not,
 * see <http://www.gnu.org/licenses/>.
 */

#ifndef VERTEX_SET_H_
#define VERTEX_SET_H_

#include <stdint.h>
#include <stdbool.h>

#include "types.h"
#include "utils.h"

/**
 * @defgroup set Set
 *
 * Data structures to represent sets and functions to manipulate them.
 *
 * The two supported representations are @ref vertex_set and @ref sparse_set.
 *
 * Vertex sets are used to represent small sets in a very compact way using
 * a single bit per entry. Optimized instructions are used to iterate over
 * them.
 *
 * Sparse sets are used for sets of integers between 0 and N. They use O(N)
 * storage, regardless of how many elements are part of the set. It allows easy
 * access to an array of all elements of the set as well as constant time
 * insertions and removals.
 */

/**
 * @addtogroup set
 * @{
 */

#define VERTEX_SET_SINGLE_WORD

#ifndef VERTEX_SET_SINGLE_WORD
/**
 * Number of 64-bit integers used to represent vertex sets.
 */
# define VERTEX_SET_NUM_WORDS 2
#else
# define VERTEX_SET_NUM_WORDS 1
#endif

/**
 * Maximum number of elements in a @ref vertex_set.
 */
#define VERTEX_SET_MAX (VERTEX_SET_NUM_WORDS * 64)

/**
 * Initializes a set of integers. Each element of this set is between 0 and @ref
 * VERTEX_SET_MAX (excluding @ref VERTEX_SET_MAX).
 */
typedef struct vertex_set {
#ifdef VERTEX_SET_SINGLE_WORD
  uint64_t data[VERTEX_SET_NUM_WORDS];
#else
  ALIGNED16 uint64_t data[VERTEX_SET_NUM_WORDS];
#endif
} vertex_set;

/**
 * Initializes a vertex set containing all possible values.
 */
static inline
void vertex_set_init_full(vertex_set *set) {
  for (int i = 0; i < VERTEX_SET_NUM_WORDS; i++)
    set->data[i] = ~((uint64_t)0ul);
}

/**
 * Initializes an empty vertex set.
 */
static inline
void vertex_set_init_empty(vertex_set *set) {
  for (int i = 0; i < VERTEX_SET_NUM_WORDS; i++)
    set->data[i] = 0;
}

/**
 * Initializes a set which contains all integers less than @p max. Max must be
 * strictly less than @ref VERTEX_SET_MAX.
 */
static inline
void vertex_set_init_up_to(vertex_set *set, uint64_t max) {

  /*
   * Fails for max = VERTEX_SET_MAX, which is fine because we do not need that
   * many vertices in the first place.
   */

#ifdef VERTEX_SET_SINGLE_WORD
  set->data[0] = (1ul << max)-1;
#else
  if (max < 64) {
    set->data[0] = (1ul << max)-1;
    set->data[1] = 0;
  }
  else {
    set->data[0] = ~(uint64_t)0ul;
    set->data[1] = (1ul << (max-64))-1;
  }
#endif
}

/**
 * Removes one element from a vertex set.
 *
 * @return True if this operation modified the set. False if @p id was not an
 * element of @p set.
 */
static inline
bool vertex_set_remove(vertex_set *set, uint32_t id) {
#ifdef VERTEX_SET_SINGLE_WORD
  bool present = (set->data[0] & (1ul << id)) != 0;
  set->data[0] &= ~(1ul << id);
#else
  bool present = (set->data[id / 64] & (1ul << (id % 64))) != 0;
  set->data[id / 64] &= ~(1ul << (id%64));
#endif

  return present;
}

/**
 * Inserts one element into a vertex set.
 *
 * @return True if this operation modified the set. False if @p id was already
 * an element of @p set.
 */
static inline
bool vertex_set_insert(vertex_set *set, uint32_t id) {
#ifdef VERTEX_SET_SINGLE_WORD
  bool present = (set->data[0] & (1ul << id)) != 0;
  set->data[0] |= (1ul << id);
#else
  bool present = (set->data[id / 64] & (1ul << (id % 64))) != 0;
  set->data[id / 64] |= (1ul << (id%64));
#endif

  return !present;
}

/**
 * @return True if @p set contains @p id.
 */
static inline
bool vertex_set_contains(const vertex_set *set, uint32_t id) {
#ifdef VERTEX_SET_SINGLE_WORD
  return (set->data[0] & (1ul << id)) != 0;
#else
  return (set->data[id / 64] & (1ul << (id % 64))) != 0;
#endif
}

/**
 * @return True if @p set contains no element.
 */
static inline
bool vertex_set_empty(const vertex_set *set) {
#ifdef VERTEX_SET_SINGLE_WORD
  return set->data[0] == 0;
#else
  return set->data[0] == 0 && set->data[1] == 0;
#endif
}

/**
 * @return True if @p set contains exactly one element.
 */
static inline
bool vertex_set_unit(const vertex_set *set) {
#ifdef VERTEX_SET_SINGLE_WORD
  return set->data[0] != 0 && (set->data[0] & (set->data[0] - 1)) == 0;
#else
  return vertex_set_size(set) == 1;
#endif
}


/**
 * @return The smallest element that contains @p set. Result is undefined for
 * empty sets.
 */
static inline
vertex_index vertex_set_min(const vertex_set *set) {
#ifdef VERTEX_SET_SINGLE_WORD
  return find_lsb64(set->data[0]);
#else
  if (set->data[0] == 0) return 64 + find_lsb64(set->data[1]);
  else return find_lsb64(set->data[0]);
#endif
}

/**
 * @return The number of elements inside the set.
 */
static inline
uint32_t vertex_set_size(const vertex_set *set) {
#ifdef VERTEX_SET_SINGLE_WORD
  return popcount64(set->data[0]);
#else
  return popcount64(set->data[0]) +
    popcount64(set->data[1]);
#endif
}

/**
 * Modifies @p set to contain the union of @p set and @p other.
 */
static inline
void vertex_set_union(vertex_set *set, const vertex_set *other) {
  for (int i = 0; i < VERTEX_SET_NUM_WORDS; i++)
    set->data[i] |= other->data[i];
}

/**
 * Removes all elements of @p other from @p set.
 */
static inline
void vertex_set_subtract(vertex_set *set, const vertex_set *other) {
  for (int i = 0; i < VERTEX_SET_NUM_WORDS; i++)
    set->data[i] &= ~other->data[i];
}

/**
 * Modifies @p set to be the intersection of @p set and @p other.
 */
static inline
void vertex_set_intersect(vertex_set *set, const vertex_set *other) {
  for (int i = 0; i < VERTEX_SET_NUM_WORDS; i++)
    set->data[i] &= other->data[i];
}

/**
 * Iterates over all elements of a set.
 *
 * This macro can replace the `for (...)` part of a loop:
 *
 * @code
 * vertex_set some_set;
 * // ...
 * VERTEX_SET_FOREACH(some_set, i) {
 *   // i is of type uint64_t
 * }
 * @endcode
 *
 * @param set The @ref vertex_set to iterate over. May be evaluated multiple
 *   times.
 * @param value Name of the variable that will contain the index of the
 *   variable.
 */
#define VERTEX_SET_FOREACH(set, value)                                  \
  for (int TOKEN_PASTE(vertex_set_it_, __LINE__) = 0;                   \
       TOKEN_PASTE(vertex_set_it_, __LINE__) < VERTEX_SET_NUM_WORDS;    \
       TOKEN_PASTE(vertex_set_it_, __LINE__)++)                         \
    for (uint64_t TOKEN_PASTE(vertex_set_contents_, __LINE__) =         \
           (set).data[TOKEN_PASTE(vertex_set_it_, __LINE__)],           \
           value;                                                       \
         TOKEN_PASTE(vertex_set_contents_, __LINE__) != 0 &&            \
           ((value = 64*TOKEN_PASTE(vertex_set_it_, __LINE__) +         \
             find_lsb64(TOKEN_PASTE(vertex_set_contents_, __LINE__))), 1); \
         TOKEN_PASTE(vertex_set_contents_, __LINE__) &=                 \
           ~(1ul << (value - 64*TOKEN_PASTE(vertex_set_it_, __LINE__))))

/**
 * @}
 */

#endif
